Determining the position and rotational orientation of an object within a defined space is a practical problem that has brought about many solutions, each dedicated toward solving the specific requirements of an application. Many technologies have been applied to position determination in one, two, and three dimensions, including optical, ultrasonic, and radio, but most methods do not provide angular orientation information such as attitude, direction, or heading. Other methods have been developed for angular measurement, but may lack positional determination.
For example, Global Positioning System (GPS) is a widely recognized position determination technology, but it lacks orientation determination capability for stationary objects. GPS operability suffers indoors from signal attenuation and reflections, so it is not a good choice for indoor applications. Ultrasonic methods that operate well indoors have been designed to replicate GPS' capability, but they, too, lack orientation determination.
Various optical methods are known to determine position and orientation. U.S. Pat. No. 5,832,139 discloses a method and apparatus for determining up to six degrees of freedom of a camera relative to a reference frame which comprises an optically modulated target with a camera and processing the camera's output video signal with a digital computer. The target may have a single pattern, multiple patterns, or patterns of varying size, and multiple targets may be used. The invention analyzes the parallax, or “warping” of square target patterns into non-square quadrilaterals within the field of view in order to determine six degrees of freedom of the camera. It does not present common bar code symbols as a choice for passively modulated targets, and does not use the inherent identity of bar code symbols for both automated means and non-automated position determination means.
Similar to the above reference, U.S. Pat. No. 5,828,770 provides a system for determining the spatial position and angular orientation of an object in real-time using activatable markers. Each marker is uniquely identified and marker relative geometry is known. The system allows low cost sensors to be used, but requires active markers, such that upon loss of power, the markers become undetectable by the sensor.
Pertaining to vehicle guidance, U.S. Pat. No. 5,367,458 discloses an apparatus and method for verifying the identity of an observed anonymous target from a plurality of anonymous targets positioned at predetermined locations within an area of operation where a guided vehicle is provided. This method offers two dimensional position and one-degree-of-freedom angular determination. Said targets are adhered to surrounding walls of the operation area, but they may become obscured in a factory or warehouse where stacks of materials may block the line of sight between detector and target.
U.S. Pat. No. 5,051,906 utilizes overhead retroreflective ceiling markers and an optical sensing means to determine a vehicle's position and orientation. Applied to mobile robots, this method includes a light source and camera that are pitched up obliquely at an angle between horizon and zenith. The markers are strip-like retroreflective features which are aligned with the axis of a hallway. In that the feature presents a pattern or alignment which is substantially parallel to a long axis of the hallway the pattern is detected and processed to derive robot navigation information. This system determines position and direction, but is aimed at directing a vehicle along a hallway, and not freely within a large area. It does not utilize self-identifying machine readable position markers.
A more sophisticated use of ceiling markers is disclosed in U.S. Pat. No. 6,556,722, wherein circular barcodes are utilized to indicate reference positions within a television studio. In this optically based method, a television studio camera is equipped with a secondary camera which views position markers set onto the studio ceiling in known locations. The markers are constructed of concentric ring barcodes which are developed specifically for the purpose. Camera position is determined by capturing an image of at least three markers and performing geometric analysis in a digital computer to determine accurate location within the three-dimensional studio space. Zoom and focus servos control the secondary camera's view and assist in marker locating. The invention discloses proprietary circular ring barcodes, which cannot be read by commercial machine vision systems, and requires a multiplicity of markers to be within view.
Three dimensional position determination is accomplished in U.S. Pat. No. 6,542,824 through the use of a portable electronic device that uses inertial sensors when GPS signals are not used. Inertial methods can provide orientation detection, but do not provide accuracy obtainable by other methods and are subject to drift through time.
In order to track vehicles indoors, a number of integrated applications have been developed wherein several technologies are used in combination to assure positional and angular measurement. For example, U.S. Pat. No. 6,859,729 discloses a combination of GPS, laser, compass, and wheel encoders to form a vehicle navigation system. Upon dropout of the GPS, the vehicle is navigated using a laser tracking system and one or both of the compass and wheel encoder detection means. The navigation system may be used to remotely control mine detection vehicles, where outdoor and indoor environments may be encountered. The system recalibrates optically with waypoint markers, and includes inertial navigation. Complexity and cost are drawbacks to implementing this method.
U.S. Pat. No. 6,732,045 detects the magnitude and angle of incremental motion vectors relating to the movement of a vehicle within a predetermined space. A plurality of sensors is used, including a laser beam with corresponding optical position markers placed at known positions and encoders which detect and encode wheel rotation and axle angular position. Vehicle position and angular orientation are determined through vector addition. Shortcomings of this invention include the assumption that wheel diameter is unchanging, that no wheel slip occurs, and that the resolution of wheel encoders is sufficient for the application. The invention requires multiple sensors, and does not provide an alternative means of determining approximate location in the event of primary system failure.
A number of machine vision-based systems exist, especially for vehicle and robot guidance, but most analyze physical surroundings by viewing downward toward floor markings, or horizontally toward local scenery or reflective markers. For example, U.S. Pat. No. 6,728,582 provides a system and method for estimating the position of an object in three dimensions using two machine vision cameras interconnected with a machine vision search tool. A nominal position for each camera's acquired image of the object is determined and a set of uncertainty vectors along each of the degrees of freedom is generated. This method requires viewing multiple objects with multiple cameras in order to make the weighted estimation.
Rotational orientation determination is not present in many position determination methods, and becomes important in applications such as vehicle tracking and vehicle guidance in order for a guidance system to properly direct the vehicle. Considering materials handling applications, goods may be stored in chosen orientations, for example with carton labels aligned in a particular direction or pallet openings aligned to facilitate lift truck access from a known direction. The combination of position determination and angular orientation determination using a single sensor is therefore desired. An improved method and apparatus must reduce or remove the shortcomings of current methods, provide general applicability, and offer high accuracy.